/*
Copyright (c) 2009 Gary Knowles

Permission is hereby granted, free of charge, to any person
obtaining a copy of this software and associated documentation
files (the "Software"), to deal in the Software without
restriction, including without limitation the rights to use,
copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following
conditions:

The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.
*/

#ifndef _LUAWANB_HASH_H_
#define _LUAWANB_HASH_H_
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string>
#include <typeinfo>

namespace LuaWanbHash {
#ifdef __BORLANDC__
typedef char * pcstring;
#else
typedef const char * pcstring;
#endif

const int sb=0x80000000;
#define onem(x,n) (((x)+(n))&0xf)
#define zerom(x,n) (onem(x,n)^0xf)
#define SB(x,n) (((((x)&(1<<n))?onem(x,n):zerom(x,n)))<<((n))*4)
//#define E(x) ((SB(x,0)|SB(x,1)|SB(x,2)|SB(x,3)|SB(x,4)|SB(x,5)|SB(x,6)|SB(x,7))&~sb)
#define El(x) (SB(x,0)|SB(x,1)|SB(x,2)|SB(x,3)|SB(x,4)|SB(x,5)|SB(x,6)|SB(x,7))
#define E(x) (((El(x)>>((x>>2)&31))^(El(x)<<(31-((x>>2)&31))))&~sb)
#define E2(x) E(x),E(1+x)
#define E4(x) E2(x),E2(2+x)
#define E8(x) E4(x),E4(4+x)
#define E16(x) E8(x),E8(8+x)
#define E32(x) E16(x),E16(16+x)
#define E64(x) E32(x),E32(32+x)
#define E128(x) E64(x),E64(64+x)
#define E256(x) E128(x),E128(128+x)
const int lut[256]={ E256(0) };

inline int Hash(const char *c,int len) {
  int r=0;
  for (int x=0;x<len;x++) {
     if ((r<<=1)&sb) r^=sb+1;
     r^=lut[(c[x]+r)&0xff];
  }
  return r;
}

inline int Hash(const std::string &s) {
   return Hash(s.c_str(),s.length());
}
inline int Hash(int i) {
    const char *c=(const char *)(&i);
    return Hash(c,sizeof(int)/sizeof(char));
}
inline int Hash(double d) {
   const char *c=(const char *)(&d);
   return Hash(c,sizeof(double)/sizeof(char));
}

// variant base class
class VarBase {
public:
   int refcount;
   int hval;
   int hv(){return hval;}
   virtual const char *tpname()=0;
   virtual std::ostream& fmt(std::ostream& os)=0;
   virtual int cmp(VarBase *r)=0; // like strcmp
   virtual ~VarBase(){};
   template <class T> int is();
   template <class T> T as(const T def);
   template <class T> T as();
   std::string as(pcstring p);
};

// nothing fancy but will work
template <class T>
class TVar: public VarBase {
public:
   T dta;
   virtual std::ostream& fmt(std::ostream& os) {
     if (is<std::string>())
       return os<<"\""<<dta<<"\"";
     else
       return os<<dta;
   }
   virtual const char *tpname() {return typeid(dta).name();}
   virtual int cmp(VarBase *r) {
      int c=strcmp(tpname(),r->tpname());
      if (c) return c;
      TVar<T> *nr=dynamic_cast<TVar<T> *>(r);
      if (dta<nr->dta) return -1;
      else if (nr->dta<dta) return 1;
      return 0;
   }
   TVar(const T &init):dta(init){hval=Hash(dta)&~0x80000000;}
};

struct NotFound {
   int operator < (const NotFound &){ return 0;}
   friend int Hash(NotFound &) { return 0;}
};

template<class T> int VarBase::is() { return (dynamic_cast< TVar<T> *>(this))?1:0;}

template<class T>
T VarBase::as(const T def) {
   TVar<T> *t=dynamic_cast<TVar<T> *>(this);
   if (t)
     return t->dta;
   return def;
}
template<class T> T VarBase::as() { return dynamic_cast<TVar<T> *>(this)->dta;}

inline std::string VarBase::as(pcstring p) { return as(std::string(p));}

// reference counted ptr class, based on
// http://www.josuttis.com/libbook/cont/countptr.hpp.html 
// made to be intrusive RCP to make more efficent
template <class T>
class RCP {
    void decref() {if (ptr) if (!(--(ptr->refcount))) delete ptr;}
  public:
    T* ptr;        // pointer to the value
    // new
    RCP (T* p=0): ptr(p) { if (ptr) ptr->refcount=1;}  
    // copy constructor
    RCP (const RCP<T>& p):ptr(p.ptr){if(ptr) ++(ptr->refcount);}
    // destructor 
    ~RCP() {decref();}
    // assignment 
    RCP<T>& operator= (const RCP<T>& p) throw() {
        if (this != &p) {
            decref();
            if (ptr = p.ptr) ++(ptr->refcount);
        }
        return *this;
    }

    // deref
    T& operator*()  const {return *ptr;}
    T* operator->() const {return ptr;}

    // some compares
    int operator==(const RCP<T>&p) {return (*ptr)==(*p.ptr);}
    int operator<(const RCP<T>&p) {return (*ptr)<(*p.ptr);}
    int operator!=(const RCP<T>&p) {return (*ptr)!=(*p.ptr);}
    T* rawptr() { return ptr;}
};
// end reference counted ptr class
// this is the variant type we will use
typedef RCP<VarBase> Var;

inline std::ostream& operator<<(std::ostream&os, const Var &v) {return v->fmt(os);}

inline int cmp(Var a, Var b) { return a->cmp(b.rawptr());}

#define MIVAR1(a) Var((VarBase *)new TVar<int>(a))
#define MIVAR2(a) MIVAR1(a),MIVAR1(a+1)
#define MIVAR4(a) MIVAR2(a),MIVAR2(a+2)
#define MIVAR8(a) MIVAR4(a),MIVAR4(a+4)
#define MIVAR16(a) MIVAR8(a),MIVAR8(a+8)
#define MIVAR32(a) MIVAR16(a),MIVAR16(a+16)
#define MIVAR64(a) MIVAR32(a),MIVAR32(a+32)
#define MIVAR128(a) MIVAR64(a),MIVAR64(a+64)
static const Var ltIvar[]={MIVAR128(0),MIVAR128(128)};
// make variant
template<class T> Var ltMV(const T &i) { return Var((VarBase *)new TVar<T>(i));}

inline Var ltMV (int i) { return (i&~255)?Var((VarBase *)new TVar<int>(i)):ltIvar[i];}

inline Var ltMV (pcstring i) { return ltMV(std::string(i));}

inline Var ltMV (Var r) { return r;}

class LT {
   public:
   class STbl {
      STbl() {
        //siz=11;
        siz=8;
        nel=0;
        hashtbl= new Tnode[siz];
        lct=0;
        nil=ltMV(NotFound());
        super=nil;
        id=(int)this;
      }
   public:
      typedef RCP<STbl> Tbl;

      int refcount;
      int lct;  // last index if this is used as a list
      Var super;
      Var nil;
      int siz,nel;
      int id;
      class Tnode {
         //static Var nil;
         public:
         Var key,val;
         int hv;
         //Tnode(){ key=nil; val=nil;hv=-1; }
         Tnode(){ hv=-1; }
         ~Tnode() {};
      };
      Tnode *hashtbl;

      virtual ~STbl() { delete []hashtbl;}
      int isprime(int a) {
         if (!(a&1)) return 0;
         int t;
         for (t=3;(t*t)<a;t+=2) if (!(a%t)) return 0;
         return 1;
      }
      void cp(Tnode *t) {
         int st,loc;
         if (t->hv==-1) return;
         st=loc=t->hv%siz;
         do {
           if (hashtbl[loc].hv==-1) {
              hashtbl[loc].key=t->key;
              hashtbl[loc].val=t->val;
              hashtbl[loc].hv=t->hv;
              break;
           }
           if ((++loc)>=siz) loc=0;
         } while(st!=loc);
      }
      void rehash() {
         Tnode *ot=hashtbl;
         int os=siz;
         siz*=2;
         //siz+=1;
         //while (!isprime(siz))
         //   siz+=2;
         hashtbl=new Tnode[siz];
         for (int x=0;x<os;x++) cp(ot+x);
         delete []ot;
      }
      class Tfind {
        public:
        int loc,found,hv;
        Var key;
        STbl *p;
        Tfind *supfind;
        Tfind(STbl *p,Var key) {supfind=NULL;this->p=p;find(key);}
        void find(const Var key) {
           int st;
           this->key=key;
           this->hv=key->hv();
           //st=loc=hv%p->siz;
           st=loc=hv&(p->siz-1);
           found=0;
           do {
             if (p->hashtbl[loc].hv==-1) break;
             if (p->hashtbl[loc].hv==hv)
                if (cmp(key,p->hashtbl[loc].key)==0)
                   { found=1;break;}
             //loc=(++loc>=p->siz)?0:loc;
             loc=(++loc)&(p->siz-1);
           } while(loc!=st);
           if (found)
              this->key=p->hashtbl[loc].key;
           else if(p->super->is<Tbl>())
              supfind=new Tfind(p->super->as<Tbl>().rawptr(),key);
        }
        ~Tfind() { if (supfind) delete supfind;}
        Var set(const Var val) {
           if (found) {
              p->hashtbl[loc].val=val;
           } else {
              p->hashtbl[loc].val=val;
              p->hashtbl[loc].key=key;
              p->hashtbl[loc].hv=hv;
              if ((++p->nel)>((p->siz*3)/4))
                p->rehash();
           }
           return val;
        }
        template<class T> T set(const T &i) { set(ltMV(i)); return i;}
        int dist(int hv, int loc) {
          int d;
          if ((d=(loc-(hv%p->siz)))<0)
             d+=p->siz;
          return d;
        }
        void del() {
           if (!found) return;
           int st=loc,hv;
           p->hashtbl[loc].key=p->nil;p->hashtbl[loc].val=p->nil;p->hashtbl[loc].hv=-1;
           if (++st>=p->siz) st=0;
           while ((hv=p->hashtbl[st].hv)!=-1) {
              if (dist(hv,loc)<dist(hv,st)) {
                 p->hashtbl[loc].key=p->hashtbl[st].key;p->hashtbl[st].key=p->nil;
                 p->hashtbl[loc].val=p->hashtbl[st].val;p->hashtbl[st].val=p->nil;
                 p->hashtbl[loc].hv=p->hashtbl[st].hv;p->hashtbl[st].hv=-1;
                 loc=st;
              }
              if (++st>=p->siz) st=0;
           }
           --p->nel;
        }
        Var get() {
          if (found) return p->hashtbl[loc].val;
          if (supfind) return supfind->get();
          return p->nil;
        }
        template<class T> T get(const T def) { return get()->as(def);}
        std::string get(pcstring def){return get(std::string(def));}
        int next(Var &k,Var &v) {
           if (found) {
              for (++loc;loc<p->siz;++loc) {
                 if (p->hashtbl[loc].hv!=-1) {
                     k=p->hashtbl[loc].key;v=p->hashtbl[loc].val; return 1;
                 }
              }
           }
           k=ltMV(NotFound()); return 0;
        }
      };
      // sugar
      template <class L,class D> D set(const L loc,const D dta) {return Tfind(this,ltMV(loc)).set(dta);}
      template <class L> std::string set(const L loc,pcstring dta) { return Tfind(this,ltMV(loc)).set(dta);}
      template <class L> void del(const L loc) {Tfind(this,ltMV(loc)).del();}
      template <class L,class D> D get(const L loc,const D def) {return Tfind(this,ltMV(loc)).get(def);}
      template <class L> std::string get(const L loc, pcstring p) { return get(loc,std::string(p));}
      template <class L> Var get(const L loc) { return Tfind(this,ltMV(loc)).get();}
      template <class L> int has(L loc) { Var v=get(loc);return (v->is<NotFound>())?0:1;}

      int atl(int l) { return (l<0)?l+lct:l;}
      template <class D> D setL(int loc,const D &dta) {return set(atl(loc),dta);}
      std::string setL(int loc,pcstring dta) {return set(atl(loc),dta);}
      void delL(int loc) {del(atl(loc));}
      template <class D> D getL(int loc,const D def) {return get(atl(loc),def);}
      std::string getL(int loc, pcstring p) { return getL(loc,std::string(p));}
      Var getL(int loc) { return get(atl(loc));}

      template <class T, class T2> STbl &i(const T k, const T2 v) { set(k,v); return *this; };

      template<class T> STbl &i(const T i) { set(lct,i);lct++;return *this;}

      STbl &setsup(const Tbl t) { super=ltMV(t);return *this;}

      Var pop() { lct--; Var r=get(lct); del(lct); return r;}

      int walknext(int &x,Var &k,Var &v) {
         for (++x;x<siz;x++) {
            if (hashtbl[x].hv!=-1) {
               k=hashtbl[x].key; v=hashtbl[x].val; return 1;
            }
         }
         k=ltMV(NotFound());
         return 0;
      }

      Tbl keys() {
        Tbl FmtSort(Tbl);
        Tbl r=Tbl(new STbl());
        for (int x=0;x<siz;x++)
           if (hashtbl[x].hv!=-1)
              r->i(hashtbl[x].key);
        return FmtSort(r);
      }
      Tbl tslice(Var a, Var b) {  // doesn't make a lot of sense with has table
         // table slice
         Tbl r=Tbl(new STbl()),ky=keys();
         Var k,v;
         if (cmp(a,b)>0) {v=b;b=a;a=v;}
         for (int x=0;x<ky->siz;x++) {
            k=ky->get(x);
            if (cmp(b,k)<0) break;
            if (cmp(a,k)<=0) r->set(k,get(k));
         }
         return r;
      }
      template<class T1, class T2> Tbl tslice(const T1 &a,const T2 &b) { return tslice(ltMV(a),ltMV(b));}
      Tbl lslice(int s, int e) { 
         Var v;STbl *r=new STbl(); if (s<0) s+=lct; if (e<0) e+=lct; 
         if (e>s) {
            for (int x=s;x<=e;++x)  if (!(v=get(x))->is<NotFound>())r->i(v); 
         }else {
            for (int x=s;x>=e;--x) if (!(v=get(x))->is<NotFound>())r->i(v); 
         }
         return Tbl(r);
      }
      Tbl reverse() {Var v;STbl *r=new STbl(); for (int x=lct-1;x>=0;x--) if(!(v=get(x))->is<NotFound>())r->i(v); return Tbl(r);}
      static STbl &op(){ STbl *r=new STbl(); return *r;}
      Tbl cl(){ return Tbl(this);}
      int len() { return lct;}
      std::ostream &fmt(std::ostream &os) {
        Var key;
        int ct=0;
        Tbl order=keys();
        os<<"{";
        for (int x=0;x<order->len();x++)  {
           key=order->get(x);
           os<<((ct++)?", ":"")<<key<<":"<<get(key);
        }
        return os<<"}";
      }
      friend int operator <  (const STbl &a, const STbl &b) { return &a<&b;}
      friend int operator == (const STbl &a, const STbl &b) { return &a==&b;}
      friend int operator != (const STbl &a, const STbl &b) { return &a!=&b;}
   };
   static STbl &op() { return STbl::op();}
};

typedef LT::STbl::Tbl Tbl;
inline int Hash(const Tbl &t) { return t->id;}
inline std::ostream& operator<<(std::ostream&os, const Tbl &v) { return v->fmt(os);}
inline std::ostream& operator<<(std::ostream&os, const NotFound &v) { return os<<"NotFound";}
//#define ltForEach(k,v,t) for (t->walkstart(k,v);!(k->is<NotFound>());t->walknext(k,v))
#define ltForEach(k,v,t) for (int _iter=-1;t->walknext(_iter,k,v);)
#define ltForEachL(v,l) for (int _iter=0;v=l->get(_iter),_iter<l->len();++_iter)

inline void swap(Tbl t, int a, int b) {Var c=t->get(a);t->set(a,t->get(b));t->set(b,c);}

inline void shellsrt( Tbl t,int st, int len,Var (*get)(Tbl,int)) {
   // shell sort from : http://mathbits.com/MathBits/CompSci/Arrays/Shell.htm
   int flag = 1, d = len, i;
   while( flag || (d>1)) {    // boolean flag (true when not equal to 0)
     flag = 0;           // reset flag to 0 to check for future swaps
     d = (d+1) / 2;
     for (i = 0; i < (len - d); i++) {
       if (cmp(get(t,i+d+st),get(t,i+st))<0) {
           swap(t,i+d+st,i+st);
           flag=1;
       }
     }
   }
}

inline void quicksort(int st, int nd, Tbl t,Var (*get)(Tbl,int)) {
  // from http://en.literateprograms.org/Quicksort_(C_Plus_Plus)
  int x;
  if ((x=((nd-st)+1))<64) { shellsrt(t,st,x,get); return;}
  x=(st+nd)/2;
  if (cmp(get(t,st),get(t,x))>0) swap(t,st,x);
  if (cmp(get(t,st),get(t,nd))>0) swap(t,st,nd);
  if (cmp(get(t,x),get(t,nd))>0) swap(t,x,nd);
  Var mid=get(t,x);
  swap(t,x,nd);
  x=st;
  for (int l=st;l<=nd;l++)
     if (cmp(mid,get(t,l))>=0) {
        swap(t,x,l);
        x++;
     }
  quicksort (st,x-1,t,get);
  quicksort (x,nd,t,get);
}

inline Var getval(Tbl t, int i) { return t->get(i);}

inline Tbl Sort(Tbl intbl, Var (*get)(Tbl,int)=getval) {
   Tbl otbl=LT::op().cl();
   Var nk;
   for(int i=0;i<intbl->len();i++) {
     nk=get(intbl,i);
     if (!(nk->is<NotFound>())) otbl->i(intbl->get(i));
   }
   quicksort(0,otbl->len()-1,otbl,get);
   return otbl;
}
#ifdef __BORLANDC__
Tbl FmtSort(Tbl i) { return Sort(i);}
#else
inline Tbl FmtSort(Tbl i) { return Sort(i);}
#endif
}
#endif

